package array;

import java.util.Arrays;

/**
 * 行或者列划分土地，分给两个开发商，二维数组商对应的value为土地的价值
 * 求两个开发商分到的土地价值总和的最小差距（行或者列只能选一种，不能即行又列）
 * @author liumingju
 * @date 2025/3/26 19:18
 */
public class 开发商购买土地 {
    public static void main(String[] args) {
        int[][] array = {
                {0, 1, 2},
                {3, 4, 5},
                {6, 7, 8}
        };
        devide(array);
    }

    /**
     * 先按照横进行划分，计算最小值的划分方式；再计算按照列进行划分，计算最小值的划分方式，最后取两者最小值
     * 递推公式:假设土地被分成2份，其中价值分别为A,B，总和为C。则B -A = C-2A。
     * 即两个开发商分配到的土地价值的差值 = 总和-2*另外一个开发商分配到的土地的总和
     * @param arr
     */
    public static void devide(int[][] arr){
        // 利用前缀和预处理数据
        int minRow = Integer.MAX_VALUE;
        int tempSum[] = new int[arr.length*arr[0].length];
        int index = 0;
        for(int i = 0;i<arr.length;i++){
            for(int j = 0;j<arr[i].length;j++){
                if(index-1<0){
                    tempSum[index] = arr[i][j];
                }else{
                    tempSum[index] = arr[i][j]+tempSum[index-1];
                }
                index++;
            }
        }
        // 利用前缀和计算按照行进行划分的最小差值计算

        // 利用前缀和计算按照列进行划分的最小差值计算

        // 返回最小的差距值

    }
}
